def findKthLargest(nums, k):
    def quick_select(nums, k):
        # 随机选择基准数
        pivot = nums[0]
        big, equal, small = [], [], []
        # 将大于、小于、等于 pivot 的元素划分至 big, small, equal 中
        for num in nums:
            if num > pivot:
                big.append(num)
            elif num < pivot:
                small.append(num)
            else:
                equal.append(num)
        if k <= len(big):
            # 第 k 大元素在 big 中，递归划分
            return quick_select(big, k)
        if len(nums) - len(small) < k:
            # 第 k 大元素在 small 中，递归划分
            return quick_select(small, k - len(nums) + len(small))
        # 第 k 大元素在 equal 中，直接返回 pivot
        return pivot

    return quick_select(nums, k)


if __name__ == '__main__':
    r = findKthLargest([1, 2, 3, 4, 5], 2)
    print(r)
